Count Ways to Score in a Game
Let's solve the Count Ways to Score in a Game problem using Dynamic Programming.
Statement#
Suppose there is a game where a player can score either
Note: You may assume that you can use a specific score as many times as you want. Additionally, the order in which we select scores from the list is significant.
Let's say the total points to be earned are
and , in three turns: . and then a , in two turns: . and then a , in two turns: .
Constraints:
<= <=
Examples#
No. | Points | Total Points | Number of Ways |
1 | [1, 2, 4] | 5 | 10 |
2 | [1, 2, 4] | 7 | 31 |
3 | [1, 2, 4] | 0 | 1 |
Try it yourself#
Implement your solution in the following playground.
Note: If you clicked the “Submit” button and the code timed out, this means that your solution needs to be optimized in terms of running time.
Hint: Use dynamic programming and see the magic.
Solution#
We will first explore the naive recursive solution to this problem and then see how it can be improved using the Recursive Numbers dynamic programming pattern.
Naive approach#
A naive approach to solving this problem would be to make all the possible permutations of available points to reach the target score, so let's first figure out the recurrence relation for this problem.
As we can only score
Number of ways to reach
, as we can then add to reach Number of ways to reach
, as we can then add to reach Number of ways to reach
, as we can then add to reach
These all are valid ways to reach a score of
As per the above points, we can derive the following recurrence relation for this problem:
Here,
Now, let's look at the code in the code widget below for the solution we just discussed.
Note: Please observe that if you include the test case commented out in the driver code, the solution is likely to time out. Try to solve the larger problem using the dynamic programming solutions provided below and see the difference.
Time complexity#
The time complexity of this solution is
Space complexity#
The space complexity of this solution is
Optimized solution using dynamic programming#
As the recursive solution to this problem is very costly, let's see if we can reduce this cost in any way. Dynamic programming helps us to avoid recomputing the same subproblems. Let's analyze our recursive solution to see if it has the properties needed for conversion to dynamic programming.
Optimal substructure: If we wanted to find the solution to the problem of counting a total score,
, given different points, and we knew the answer to the subproblems formed by subtracting each of the points from the total score S, we could simply sum up the answer to these subproblems, and that would give us the answer to our original problem. Therefore, this problem obeys the optimal substructure property. Overlapping subproblems: The algorithm solves the same subproblems again and again, so it does have the second property of dynamic programming as well.
Top-down solution#
The top-down solution, commonly known as the memoization technique, is an enhancement of the recursive solution. It overcomes the problem of calculating solutions to subproblems over and over again by storing the subproblem solutions, and reusing the stored solutions when the same subproblem is encountered again. Therefore, the only addition to this algorithm compared to the simple recursive one is the addition of memoization. Specifically, we build the solution top-down and store the found results in a memo array.
The slides below are to help you visualize the process. Here, the green nodes represent recursive calls where stored results are fetched from the memo array:
1 of 16
2 of 16
3 of 16
4 of 16
5 of 16
6 of 16
7 of 16
8 of 16
9 of 16
10 of 16
11 of 16
12 of 16
13 of 16
14 of 16
15 of 16
16 of 16
Now, let's look at the code in the code widget below for the solution we just discussed.
Note: Please observe that if you now uncomment the large test case in the driver code, the dynamic programming solution will still work.
Time complexity#
The time complexity of this solution is
Space complexity#
The space complexity of this solution is
Bottom-up solution#
Let’s look at the bottom-up dynamic programming approach to solving this problem. The bottom-up solution, also known as the tabulation technique, is an iterative method of solving dynamic programming problems. Here, we iteratively build the solution in a bottom-up direction by storing the results in a fixed-size array.
We first create and initialize the fixed array, dp, that will store our results. Then, we set dp[0] to 1, which is our base case, that is, there is only one way to reach a score of
To calculate the result for any turn, we sum up the number of ways to get a score of dp[5-1], dp[5-2] and dp[5-4]. During the calculations, if at any point, the remaining value needed to reach
Let's look at how this technique works for a total score of
1 of 10
2 of 10
3 of 10
4 of 10
5 of 10
6 of 10
7 of 10
8 of 10
9 of 10
10 of 10
Let's have a look at the code for the bottom-up approach as well.
Number Factors
Unique Paths to Goal